/*
 * Copyright (C) 2010 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkNotNull;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtCompatible;
import com.google.common.base.Function;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.RandomAccess;

import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * Static methods pertaining to sorted {@link List} instances.
 *
 * <p>In this documentation, the terms <i>greatest</i>, <i>greater</i>, <i>least</i>, and
 * <i>lesser</i> are considered to refer to the comparator on the elements, and the terms
 * <i>first</i> and <i>last</i> are considered to refer to the elements' ordering in a list.
 *
 * @author Louis Wasserman
 */
@GwtCompatible
@Beta
@ElementTypesAreNonnullByDefault
final class SortedLists
{
    private SortedLists()
    {
    }

    /**
     * A specification for which index to return if the list contains at least one element that
     * compares as equal to the key.
     */
    enum KeyPresentBehavior
    {
        /**
         * Return the index of any list element that compares as equal to the key. No guarantees are
         * made as to which index is returned, if more than one element compares as equal to the key.
         */
        ANY_PRESENT
                {
                    @Override
                    <E extends @Nullable Object> int resultIndex(
                            Comparator<? super E> comparator,
                            @ParametricNullness E key,
                            List<? extends E> list,
                            int foundIndex)
                    {
                        return foundIndex;
                    }
                },
        /**
         * Return the index of the last list element that compares as equal to the key.
         */
        LAST_PRESENT
                {
                    @Override
                    <E extends @Nullable Object> int resultIndex(
                            Comparator<? super E> comparator,
                            @ParametricNullness E key,
                            List<? extends E> list,
                            int foundIndex)
                    {
                        // Of course, we have to use binary search to find the precise
                        // breakpoint...
                        int lower = foundIndex;
                        int upper = list.size() - 1;
                        // Everything between lower and upper inclusive compares at >= 0.
                        while (lower < upper)
                        {
                            int middle = (lower + upper + 1) >>> 1;
                            int c = comparator.compare(list.get(middle), key);
                            if (c > 0)
                            {
                                upper = middle - 1;
                            }
                            else
                            { // c == 0
                                lower = middle;
                            }
                        }
                        return lower;
                    }
                },
        /**
         * Return the index of the first list element that compares as equal to the key.
         */
        FIRST_PRESENT
                {
                    @Override
                    <E extends @Nullable Object> int resultIndex(
                            Comparator<? super E> comparator,
                            @ParametricNullness E key,
                            List<? extends E> list,
                            int foundIndex)
                    {
                        // Of course, we have to use binary search to find the precise
                        // breakpoint...
                        int lower = 0;
                        int upper = foundIndex;
                        // Of course, we have to use binary search to find the precise breakpoint...
                        // Everything between lower and upper inclusive compares at <= 0.
                        while (lower < upper)
                        {
                            int middle = (lower + upper) >>> 1;
                            int c = comparator.compare(list.get(middle), key);
                            if (c < 0)
                            {
                                lower = middle + 1;
                            }
                            else
                            { // c == 0
                                upper = middle;
                            }
                        }
                        return lower;
                    }
                },
        /**
         * Return the index of the first list element that compares as greater than the key, or {@code
         * list.size()} if there is no such element.
         */
        FIRST_AFTER
                {
                    @Override
                    public <E extends @Nullable Object> int resultIndex(
                            Comparator<? super E> comparator,
                            @ParametricNullness E key,
                            List<? extends E> list,
                            int foundIndex)
                    {
                        return LAST_PRESENT.resultIndex(comparator, key, list, foundIndex) + 1;
                    }
                },
        /**
         * Return the index of the last list element that compares as less than the key, or {@code -1}
         * if there is no such element.
         */
        LAST_BEFORE
                {
                    @Override
                    public <E extends @Nullable Object> int resultIndex(
                            Comparator<? super E> comparator,
                            @ParametricNullness E key,
                            List<? extends E> list,
                            int foundIndex)
                    {
                        return FIRST_PRESENT.resultIndex(comparator, key, list, foundIndex) - 1;
                    }
                };

        abstract <E extends @Nullable Object> int resultIndex(
                Comparator<? super E> comparator,
                @ParametricNullness E key,
                List<? extends E> list,
                int foundIndex);
    }

    /**
     * A specification for which index to return if the list contains no elements that compare as
     * equal to the key.
     */
    enum KeyAbsentBehavior
    {
        /**
         * Return the index of the next lower element in the list, or {@code -1} if there is no such
         * element.
         */
        NEXT_LOWER
                {
                    @Override
                    int resultIndex(int higherIndex)
                    {
                        return higherIndex - 1;
                    }
                },
        /**
         * Return the index of the next higher element in the list, or {@code list.size()} if there is
         * no such element.
         */
        NEXT_HIGHER
                {
                    @Override
                    public int resultIndex(int higherIndex)
                    {
                        return higherIndex;
                    }
                },
        /**
         * Return {@code ~insertionIndex}, where {@code insertionIndex} is defined as the point at which
         * the key would be inserted into the list: the index of the next higher element in the list, or
         * {@code list.size()} if there is no such element.
         *
         * <p>Note that the return value will be {@code >= 0} if and only if there is an element of the
         * list that compares as equal to the key.
         *
         * <p>This is equivalent to the behavior of {@link java.util.Collections#binarySearch(List,
         * Object)} when the key isn't present, since {@code ~insertionIndex} is equal to {@code -1 -
         * insertionIndex}.
         */
        INVERTED_INSERTION_INDEX
                {
                    @Override
                    public int resultIndex(int higherIndex)
                    {
                        return ~higherIndex;
                    }
                };

        abstract int resultIndex(int higherIndex);
    }

    /**
     * Searches the specified naturally ordered list for the specified object using the binary search
     * algorithm.
     *
     * <p>Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior,
     * KeyAbsentBehavior)} using {@link Ordering#natural}.
     */
    public static <E extends Comparable> int binarySearch(
            List<? extends E> list,
            E e,
            KeyPresentBehavior presentBehavior,
            KeyAbsentBehavior absentBehavior)
    {
        checkNotNull(e);
        return binarySearch(list, e, Ordering.natural(), presentBehavior, absentBehavior);
    }

    /**
     * Binary searches the list for the specified key, using the specified key function.
     *
     * <p>Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior,
     * KeyAbsentBehavior)} using {@link Ordering#natural}.
     */
    public static <E extends @Nullable Object, K extends Comparable> int binarySearch(
            List<E> list,
            Function<? super E, K> keyFunction,
            K key,
            KeyPresentBehavior presentBehavior,
            KeyAbsentBehavior absentBehavior)
    {
        checkNotNull(key);
        return binarySearch(
                list, keyFunction, key, Ordering.natural(), presentBehavior, absentBehavior);
    }

    /**
     * Binary searches the list for the specified key, using the specified key function.
     *
     * <p>Equivalent to {@link #binarySearch(List, Object, Comparator, KeyPresentBehavior,
     * KeyAbsentBehavior)} using {@link Lists#transform(List, Function) Lists.transform(list,
     * keyFunction)}.
     */
    public static <E extends @Nullable Object, K extends @Nullable Object> int binarySearch(
            List<E> list,
            Function<? super E, K> keyFunction,
            @ParametricNullness K key,
            Comparator<? super K> keyComparator,
            KeyPresentBehavior presentBehavior,
            KeyAbsentBehavior absentBehavior)
    {
        return binarySearch(
                Lists.transform(list, keyFunction), key, keyComparator, presentBehavior, absentBehavior);
    }

    /**
     * Searches the specified list for the specified object using the binary search algorithm. The
     * list must be sorted into ascending order according to the specified comparator (as by the
     * {@link Collections#sort(List, Comparator) Collections.sort(List, Comparator)} method), prior to
     * making this call. If it is not sorted, the results are undefined.
     *
     * <p>If there are elements in the list which compare as equal to the key, the choice of {@link
     * KeyPresentBehavior} decides which index is returned. If no elements compare as equal to the
     * key, the choice of {@link KeyAbsentBehavior} decides which index is returned.
     *
     * <p>This method runs in log(n) time on random-access lists, which offer near-constant-time
     * access to each list element.
     *
     * @param list            the list to be searched.
     * @param key             the value to be searched for.
     * @param comparator      the comparator by which the list is ordered.
     * @param presentBehavior the specification for what to do if at least one element of the list
     *                        compares as equal to the key.
     * @param absentBehavior  the specification for what to do if no elements of the list compare as
     *                        equal to the key.
     * @return the index determined by the {@code KeyPresentBehavior}, if the key is in the list;
     * otherwise the index determined by the {@code KeyAbsentBehavior}.
     */
    public static <E extends @Nullable Object> int binarySearch(
            List<? extends E> list,
            @ParametricNullness E key,
            Comparator<? super E> comparator,
            KeyPresentBehavior presentBehavior,
            KeyAbsentBehavior absentBehavior)
    {
        checkNotNull(comparator);
        checkNotNull(list);
        checkNotNull(presentBehavior);
        checkNotNull(absentBehavior);
        if (!(list instanceof RandomAccess))
        {
            list = Lists.newArrayList(list);
        }
        // TODO(lowasser): benchmark when it's best to do a linear search

        int lower = 0;
        int upper = list.size() - 1;

        while (lower <= upper)
        {
            int middle = (lower + upper) >>> 1;
            int c = comparator.compare(key, list.get(middle));
            if (c < 0)
            {
                upper = middle - 1;
            }
            else if (c > 0)
            {
                lower = middle + 1;
            }
            else
            {
                return lower
                        + presentBehavior.resultIndex(
                        comparator, key, list.subList(lower, upper + 1), middle - lower);
            }
        }
        return absentBehavior.resultIndex(lower);
    }
}
